#include "gobang.h"


Gobang::Gobang() {
	board = vector<vector<char>>(SIZE, vector<char>(SIZE, '.'));
	currentPlayer = 'O';
	historyO.reserve(SIZE * SIZE);
	historyX.reserve(SIZE * SIZE);
	scoreRecordTable = vector<vector<vector<int>>>(SIZE, vector<vector<int>>(SIZE, vector<int>(4, 0)));
	alphaBetaCalls = 0;
	alphaBetaCutoffs = 0;
}

// 打印棋盘
void Gobang::printBoard() {
	cout << "  ";
	for (int i = 0; i < SIZE; i++) {
		cout << (i < 10 ? " " : "") << i << " ";
	}
	cout << endl;

	for (int i = 0; i < SIZE; i++) {
		cout << (i < 10 ? " " : "") << i << " ";
		for (int j = 0; j < SIZE; j++) {
			cout << board[i][j] << "  ";
		}
		cout << endl;
	}
}

// 是否在影响范围内，-1表示不在，否则返回方向索引
int Gobang::isInInfluenceArea(int row1, int col1, int row2, int col2) {
	if (max(abs(row1 - row2), abs(col1 - col2)) > 6) {
		return -1;
	}
	// delta row = +-delta col 说明在同一条对角线上
	if (col1 - col2 == row2 - row1) {
		return 3;
	}
	if (col1 - col2 == row1 - row2) {
		return 2;
	}
	// 在同一行或同一列
	if (row1 == row2) {
		return 0;
	}
	if (col1 == col2) {
		return 1;
	}
	else {
		return -1;
	}
}

// 检查是否胜利
bool Gobang::checkWin(int row, int col, char player) {
	// 四个方向的计数

	for (auto& dir : directions) {
		int count = 1;
		int dx = dir[0];
		int dy = dir[1];

		// 正方向
		for (int i = 1; i < 5; i++) {
			int newRow = row + i * dx;
			int newCol = col + i * dy;
			if (newRow >= 0 && newRow < SIZE && newCol >= 0 && newCol < SIZE &&
				board[newRow][newCol] == player) {
				count++;
			}
			else {
				break;
			}
		}

		// 反方向
		for (int i = 1; i < 5; i++) {
			int newRow = row - i * dx;
			int newCol = col - i * dy;
			if (newRow >= 0 && newRow < SIZE && newCol >= 0 && newCol < SIZE &&
				board[newRow][newCol] == player) {
				count++;
			}
			else {
				break;
			}
		}

		if (count >= 5) return true;
	}
	return false;
}

// 检查棋盘是否已满
bool Gobang::isBoardFull() {
	return (historyO.size() + historyX.size()) >= (SIZE * SIZE);
}

char Gobang::getCurrentPlayer() {
	return currentPlayer;
}

// 下棋
GameState Gobang::play(int row, int col) {
	if (!isValidMove(row, col)) {
		cout << "无效的坐标: " << row << ", " << col << endl;
		return GameState::InvalidMove;
	}
	board[row][col] = currentPlayer;
	// 记录历史
	if (currentPlayer == 'O') {
		historyO.push_back({ row, col });
	}
	else {
		historyX.push_back({ row, col });
	}
	// 更新邻居 删除落子点，添加周围8个空的点
	//for (int i = -1; i <= 1; i++) {
	//	for (int j = -1; j <= 1; j++) {
	//		int newRow = row + i;
	//		int newCol = col + j;
	//		if (isValidMove(newRow, newCol)) {
	//			neighbors.insert({ newRow, newCol });
	//		}
	//	}
	//}
	//neighbors.erase({ row, col });
	
	// 更新分数表
	if (currentPlayer == 'O') {
		for (int i = 0; i < 4; i++) {
			ScoreO += evaluate_point(row, col, i);
			//ScoreX = ScoreX - evaluate_point(row, col, i) * enermy_ratio;
			scoreRecordTable[row][col][i] = evaluate_point(row, col, i);
		}
	}
	else {
		for (int i = 0; i < 4; i++) {
			ScoreX += evaluate_point(row, col, i);
			//ScoreO = ScoreO - evaluate_point(row, col, i) * enermy_ratio;
			scoreRecordTable[row][col][i] = evaluate_point(row, col, i);
		}
	}
	for (const auto& point : historyO) {
		int direction = isInInfluenceArea(row, col, point.first, point.second);
		if (direction == -1) {
			continue;
		}
		int score = evaluate_point(point.first, point.second, direction);
		ScoreO += score - scoreRecordTable[point.first][point.second][direction];
		//ScoreX = ScoreX - (score - scoreRecordTable[point.first][point.second][direction]) * enermy_ratio;
		scoreRecordTable[point.first][point.second][direction] = score;
	}
	for (const auto& point : historyX) {
		int direction = isInInfluenceArea(row, col, point.first, point.second);
		if (direction == -1) {
			continue;
		}
		int score = evaluate_point(point.first, point.second, direction);
		ScoreX += score - scoreRecordTable[point.first][point.second][direction];
		//ScoreO = ScoreO - (score - scoreRecordTable[point.first][point.second][direction]) * enermy_ratio;
		scoreRecordTable[point.first][point.second][direction] = score;
	}
	//scoreRecordTableList.push_back(scoreRecordTable);

	// 判断胜负
	if (checkWin(row, col, currentPlayer)) {
		if (currentPlayer == 'O') {
			hasWin = true;
			currentPlayer = (currentPlayer == 'O' ? 'X' : 'O');
			return GameState::O_Win;
		}
		else {
			hasWin = true;
			currentPlayer = (currentPlayer == 'O' ? 'X' : 'O');
			return GameState::X_Win;
		}
	}
	else if (isBoardFull()) {
		currentPlayer = (currentPlayer == 'O' ? 'X' : 'O');
		return GameState::Draw;
	}
	else {
		currentPlayer = (currentPlayer == 'O' ? 'X' : 'O');
		return GameState::OnGoing;
	}
}

// 悔棋
void Gobang::undo() {
	// 清除历史
	currentPlayer = (currentPlayer == 'O' ? 'X' : 'O');
	if (hasWin) {
		hasWin = false;
	}
	pair<int, int> point;
	if (currentPlayer == 'O') {
		point = historyO.back();
		historyO.pop_back();
		board[point.first][point.second] = '.';
	}
	else {
		point = historyX.back();
		historyX.pop_back();
		board[point.first][point.second] = '.';
	}
	int row = point.first;
	int col = point.second;
	// 更新分数表
	for (const auto& point : historyO) {
		int direction = isInInfluenceArea(row, col, point.first, point.second);
		if (direction == -1) {
			continue;
		}
		int score = evaluate_point(point.first, point.second, direction);
		ScoreO += score - scoreRecordTable[point.first][point.second][direction];
		//ScoreX = ScoreX - (score - scoreRecordTable[point.first][point.second][direction]) * enermy_ratio;
		scoreRecordTable[point.first][point.second][direction] = score;
	}
	for (const auto& point : historyX) {
		int direction = isInInfluenceArea(row, col, point.first, point.second);
		if (direction == -1) {
			continue;
		}
		int score = evaluate_point(point.first, point.second, direction);
		ScoreX += score - scoreRecordTable[point.first][point.second][direction];
		//ScoreO = ScoreO - (score - scoreRecordTable[point.first][point.second][direction]) * enermy_ratio;
		scoreRecordTable[point.first][point.second][direction] = score;
	}
	for (int direction = 0; direction < 4; direction++) {
		if (currentPlayer == 'O') {
			ScoreO -= scoreRecordTable[row][col][direction];
			//ScoreX -= scoreRecordTable[row][col][direction];
			scoreRecordTable[row][col][direction] = 0;
		}
		else {
			ScoreX -= scoreRecordTable[row][col][direction];
			//ScoreO -= scoreRecordTable[row][col][direction];
			scoreRecordTable[row][col][direction] = 0;
		}

	}

}

// 检查落子是否合法
bool Gobang::isValidMove(int row, int col) {
	return row >= 0 && row < SIZE && col >= 0 && col < SIZE && board[row][col] == '.';
}

const vector<vector<char>>& Gobang::getBoard() {
	return board;
}

const vector<pair<vector<char>, int>> Gobang::scoreTable = {
	{{'O','O','O','O','O'}, 50000},
	{{'.','O','O','O','O','.'}, 5000},
	{{'.','O','O','O','.','.'}, 500},
	{{'.','.','O','O','O','.'}, 500},
	{{'.','O','O','.','O','.'}, 500},
	{{'.','O','.','O','O','.'}, 500},
	{{'O','O','O','O','.'}, 500},
	{{'.','O','O','O','O'}, 500},
	{{'O','O','.','O','O'}, 500},
	{{'O','.','O','O','O'}, 500},
	{{'O','O','O','.','O'}, 500},
	{{'.','.','O','O','.','.'}, 50},
	{{'.','.','O','.','O','.'}, 50},
	{{'.','O','.','O','.','.'}, 50},
	{{'.','.','.','O','.','.'}, 5},
	{{'.','.','O','.','.','.'}, 5},
};

int Gobang::evaluate_point(int row, int col, int direction) {
	int score = 0;
	char player = board[row][col];
	int directionX = directions[direction][0];
	int directionY = directions[direction][1];
	vector<char> pattern(9);

	// 在当前方向上前后各取4格，共9格
	for (int offset = -4; offset <= 4; ++offset) {
		int newRow = row + offset * directionX;
		int newCol = col + offset * directionY;
		if (newRow >= 0 && newRow < SIZE && newCol >= 0 && newCol < SIZE) {
			if (board[newRow][newCol] == player) {
				pattern.push_back('O');
			}
			else if (board[newRow][newCol] == '.') {
				pattern.push_back('.');
			}
			else {
				pattern.push_back('X');
			}
		}
		else {
			pattern.push_back('X');
		}
	}

	for (const auto& entry : scoreTable) {
		if (matchPattern(pattern, entry.first)) {
			score = entry.second;
			break;
		}
	}
	return score;
}

int Gobang::alphaBeta(int alpha, int beta, int depth, bool isMaxmizing, char maxmizingPlayer) {
	auto emptyCells = getNeighborCells();
	int count = 0;
	alphaBetaCalls += 1;
	if (depth <= 0 || emptyCells.size() == 0 || hasWin) {
		return maxmizingPlayer == 'O' ? ScoreO - ScoreX * enermy_ratio : ScoreX - ScoreO * enermy_ratio;
	}
	if (isMaxmizing) {
		int maxScore = INT_MIN;
		pair<int, int> bestMove = { -1, -1 };
		auto scoredCells = sortCells(emptyCells, maxmizingPlayer);
		for (const auto& cell : scoredCells) {
			int i = cell.second.first;
			int j = cell.second.second;
			play(i, j);
			int score = alphaBeta(alpha, beta, depth - 1, false, maxmizingPlayer);
			undo();
			if (score > maxScore) {
				maxScore = score;
				bestMove = { i, j };
			}
			alpha = max(alpha, score);
			if (beta <= alpha) {
				alphaBetaCutoffs += 1;
				break;
			}
			if (count++ > 10) {
				break;
			}
		}
		return maxScore;
	}
	else {
		int minScore = INT_MAX;
		pair<int, int> bestMove = { -1, -1 };
		auto scoredCells = sortCells(emptyCells, maxmizingPlayer == 'O' ? 'X' : 'O');
		for (const auto& cell : scoredCells) {
			int i = cell.second.first;
			int j = cell.second.second;
			play(i, j);
			int score = alphaBeta(alpha, beta, depth - 1, true, maxmizingPlayer);
			undo();
			if (score < minScore) {
				minScore = score;
				bestMove = { i, j };
			}
			beta = min(beta, score);
			if (beta <= alpha) {
				alphaBetaCutoffs += 1;
				break;
			}
			if (count++ > 10) {
				break;
			}
		}
		return minScore;
	}
}

vector<pair<int, pair<int, int>>> Gobang::sortCells(const set<pair<int, int>>& emptyCells, char player) {
    vector<pair<int, pair<int, int>>> scoredCells;
	scoredCells.reserve(emptyCells.size());
    // 遍历board，使用evaluate得到每个空位置的分数
    for (const auto& cell : emptyCells) {
		play(cell.first, cell.second);
        int score = player == 'O' ? ScoreO - enermy_ratio * ScoreX : ScoreX - enermy_ratio * ScoreO;
		undo();
        scoredCells.push_back({ score, {cell.first, cell.second} });
    }

    // 根据分数对emptyCells进行排序
    sort(scoredCells.begin(), scoredCells.end(), [](const auto& a, const auto& b) {
        return a.first > b.first;
        });
    return scoredCells;
}

pair<int, int> Gobang::bestMove(char player) {
	auto emptyCells = getNeighborCells();
	int bestScore = INT_MIN;
	pair<int, int> bestMove = { -1, -1 };
	auto scoredCells = sortCells(emptyCells, player);
	int count = 0;
	for (const auto& scoredCell : scoredCells) {
		const auto& cell = scoredCell;
		play(cell.second.first, cell.second.second);
		int score = alphaBeta(INT_MIN, INT_MAX, difficulty - 1, false, player);
		undo();
		if (score > bestScore) {
			bestScore = score;
			bestMove = cell.second;
		}
		cout << "Move: (" << cell.second.first << ", " << cell.second.second << ") Score: " << score << " Best Score: " << bestScore << " Best Move: (" << bestMove.first << ", " << bestMove.second << ")" << endl;
		if (count++ > 10) {
			break;
		}
	}
	cout << "AlphaBeta Calls: " << alphaBetaCalls << " AlphaBeta Cutoffs: " << alphaBetaCutoffs << endl;
	//cout << "MinMax Calls: " << minMaxCalls << endl;
	return bestMove;
}

set<pair<int, int>> Gobang::getNeighborCells() {
	set<pair<int, int>> result;
	for (const auto& point : historyO) {
		int row = point.first;
		int col = point.second;
		for (int i = -1; i <= 1; i++) {
			for (int j = -1; j <= 1; j++) {
				int newRow = row + i;
				int newCol = col + j;
				if (isValidMove(newRow, newCol)) {
					result.insert({ newRow, newCol });
				}
			}
		}
	}
	for (const auto& point : historyX) {
		int row = point.first;
		int col = point.second;
		for (int i = -1; i <= 1; i++) {
			for (int j = -1; j <= 1; j++) {
				int newRow = row + i;
				int newCol = col + j;
				if (isValidMove(newRow, newCol)) {
					result.insert({ newRow, newCol });
				}
			}
		}
	}

	return result;
}

void Gobang::printScoreRecord() {
	cout << "ScoreO: " << ScoreO << " ScoreX: " << ScoreX << endl;
	for (int i = 0; i < SIZE; i++) {
		for (int j = 0; j < SIZE; j++) {
			int score = 0;
			for (int k = 0; k < 4; k++) {
				score += scoreRecordTable[i][j][k];
			}
			cout << setw(6) << score << ' ';
		}
		cout << endl;
	}
}

string Gobang::getScoreRecordTable() {
	string result;
	for (int i = 0; i < SIZE; i++) {
		for (int j = 0; j < SIZE; j++) {
			int score = 0;
			for (int k = 0; k < 4; k++) {
				score += scoreRecordTable[i][j][k];
			}
			result += to_string(score) + " ";
		}
		result += "\n";
	}

	return result;
}

void Gobang::setDifficulty(int difficulty) {
	this->difficulty = difficulty;
}

bool Gobang::matchPattern(const std::vector<char>& vec, const std::vector<char>& pattern) {
	size_t longSize = vec.size();
	size_t patternSize = pattern.size();

	// 遍历长vector的每个可能的起始位置
	for (size_t i = 0; i <= longSize - patternSize; ++i) {
		bool match = true;
		// 检查从当前位置开始的子序列是否与模板匹配
		for (size_t j = 0; j < patternSize; ++j) {
			if (vec[i + j] != pattern[j]) {
				match = false;
				break;
			}
		}
		if (match) {
			return true; // 找到匹配的子序列
		}
	}
	return false; // 没有找到匹配的子序列
}

void Gobang::get1dBoard(std::vector<unsigned char>& res){
	res.reserve(SIZE*SIZE);
	res.clear();
	for(const auto& row : board){
		for(const auto& element : row){
			res.push_back(element);
		}
	}
	return;
}